package com.zto.sch.advance.algorithms;

import com.zto.sch.base.util.CommonUtil;

import java.util.Arrays;

/**
 * @program: sch-diy-parent
 * @description:
 * @author: sch
 * @create: 2021-01-17 10:47
 **/
public class BinarchSearch {

    public static void main(String[] args) {
        int[] arr = CommonUtil.getArray(500000000);
//        Arrays.sort(arr);
//        printArr(arr);
        int key = 10;
        int indexExit = binarchSearch(arr, key);

        System.out.println(key + "在数组织中的索引位置是:" + indexExit);
    }

    /**
     * 思路：
     * 1，有序数组
     * 2，拿要查的值[key]与中间位置的值[mid]比较
     * 3，key<min 递归左侧数据，key>min 递归右侧数组。key=min 直接返回
     * 4，重复2，3
     * 5，若没查到，返回-1
     */
    private static int binarchSearch(int[] arr, int key) {
        int start = 0, end = arr.length;

        return findIndexArr(arr, start, end, key);
    }

    private static int findIndexArr(int[] arr, int start, int end, int key) {
        while (start <= end) {
            int mid = (start + end) >> 1;
            if (arr[mid] > key) {
                end = mid - 1;
            } else if (arr[mid] < key) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    private static void printArr(int[] arr) {
        for (int a : arr) {
            System.out.print(a + ",");
        }
        System.out.println("");
    }
}
